GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Isomorphie von Graphen</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Isomorphie von Graphen</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Die <b>Isomorphie von Graphen</b> (oder <b>Graphenisomorphie</b>) ist in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> die Eigenschaft zweier <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graphen</a>, strukturell gleich zu sein.

</p><p>Bei der Untersuchung graphentheoretischer Probleme kommt es meist nur auf die Struktur der Graphen, nicht aber auf die Bezeichnung ihrer Knoten an. In den allermeisten Fällen sind die untersuchten Grapheneigenschaften dann invariant bzgl. <a href="Isomorphismus" title="Isomorphismus">Isomorphie</a> (<a href="Altgriechische_Sprache" title="Altgriechische Sprache">gr.</a> ἴσος <i>ísos</i> „gleich“ und μορφή <i>morphé</i> „Form“, „Gestalt“), die im Folgenden genauer definiert wird.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definitionen">Definitionen</h2></div>

<p>Seien <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}=\left(V_{1},E_{1}\right)}">

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}=\left(V_{1},E_{1}\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/62966e855289c331a2702d576eb0e58b3ce02cec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{1}=\left(V_{1},E_{1}\right)}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}=\left(V_{2},E_{2}\right)}">

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}=\left(V_{2},E_{2}\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c737ecc4a49e690b59ce882f0dde856e580d3666.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{2}=\left(V_{2},E_{2}\right)}" loading="lazy"></span> Graphen desselben <a href="Typen_von_Graphen_in_der_Graphentheorie" class="mw-redirect" title="Typen von Graphen in der Graphentheorie">Typs</a>. Eine <a href="Bijektive_Abbildung" class="mw-redirect" title="Bijektive Abbildung">bijektive Abbildung</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\colon V_{1}\to V_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\colon V_{1}\to V_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d7b6853cbb7ebfbc0661014c344cb740d931639e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:10.726ex; height:2.509ex;" alt="{\displaystyle p\colon V_{1}\to V_{2}}" loading="lazy"></span> heißt <b>Isomorphismus</b> zwischen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy"></span>, falls gilt:

</p>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\{v,w\right\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7b7ef04dabb651a4b4b0bd50533644a97a3492ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.151ex; height:2.843ex;" alt="{\displaystyle \left\{v,w\right\}}" loading="lazy"></span> ist Kante von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"></span> genau dann, wenn <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\{p(v),p(w)\right\}}">

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\{p(v),p(w)\right\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fe882129221bba032ad3b39d8e09729cc6f0ea91.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.108ex; height:2.843ex;" alt="{\displaystyle \left\{p(v),p(w)\right\}}" loading="lazy"></span> Kante von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy"></span> ist in <a href="Ungerichteter_Graph" class="mw-redirect" title="Ungerichteter Graph">ungerichteten Graphen</a> <a href="Graph_ohne_Mehrfachkanten" class="mw-redirect" title="Graph ohne Mehrfachkanten">ohne Mehrfachkanten</a>.</li>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(v,w\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/11300d4fdce5180df0534851151f6bfa338b3d41.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.635ex; height:2.843ex;" alt="{\displaystyle \left(v,w\right)}" loading="lazy"></span> ist Kante von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"></span> genau dann, wenn <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left(p\left(v\right),p\left(w\right)\right)}">

<mrow>

<mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(p\left(v\right),p\left(w\right)\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/214d6ff9e41786a3035493f15e506c5d2b4adac8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.754ex; height:2.843ex;" alt="{\displaystyle \left(p\left(v\right),p\left(w\right)\right)}" loading="lazy"></span> Kante von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy"></span> ist in <a href="Gerichteter_Graph" title="Gerichteter Graph">gerichteten Graphen</a> ohne Mehrfachkanten.</li>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{1}\left(\left\{v,w\right\}\right)=E_{2}\left(\left\{p\left(v\right),p\left(w\right)\right\}\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b33bb6ff66eaca23ff1228e68e0fbec77a05369.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.45ex; height:2.843ex;" alt="{\displaystyle E_{1}\left(\left\{v,w\right\}\right)=E_{2}\left(\left\{p\left(v\right),p\left(w\right)\right\}\right)}" loading="lazy"></span> in ungerichteten <a href="Graph_mit_Mehrfachkanten" class="mw-redirect" title="Graph mit Mehrfachkanten">Graphen mit Mehrfachkanten</a>, d. h., je zwei Ecken sind mit ebenso vielen Kanten verbunden wie ihre Bildecken.</li>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{1}\left(\left(v,w\right)\right)=E_{2}\left(\left(p\left(v\right),p\left(w\right)\right)\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2437a6b55e5bcf8253d4f3540d787dcf1310771f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.419ex; height:2.843ex;" alt="{\displaystyle E_{1}\left(\left(v,w\right)\right)=E_{2}\left(\left(p\left(v\right),p\left(w\right)\right)\right)}" loading="lazy"></span> in gerichteten Graphen mit Mehrfachkanten.</li>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\{v_{1},\dotsc ,v_{k}\right\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a69ca1725e7db590bfa0d162cc78b9fbdadcc063.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.901ex; height:2.843ex;" alt="{\displaystyle \left\{v_{1},\dotsc ,v_{k}\right\}}" loading="lazy"></span> ist Kante von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"></span> genau dann, wenn <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\{p\left(v_{1}\right),\dotsc ,p\left(v_{k}\right)\right\}}">

<mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\{p\left(v_{1}\right),\dotsc ,p\left(v_{k}\right)\right\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/db06c5688fd80ebd7f8f0ae246bb681c77ac991c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.02ex; height:2.843ex;" alt="{\displaystyle \left\{p\left(v_{1}\right),\dotsc ,p\left(v_{k}\right)\right\}}" loading="lazy"></span> Kante von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy"></span> ist in <a href="Hypergraph" class="mw-redirect" title="Hypergraph">Hypergraphen</a>.</li></ul>

<p>Zwei Graphen heißen zueinander <b>isomorph,</b> falls es einen Isomorphismus zwischen ihnen gibt. Die Abbildung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span> heißt <b>Automorphismus</b> von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"></span> bzw. <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy"></span>, falls zusätzlich <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}=G_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}=G_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cbec328d1a70d415a533b1de9c5fdc0dd7605cbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.86ex; height:2.509ex;" alt="{\displaystyle G_{1}=G_{2}}" loading="lazy"></span> gilt.

</p>

<div class="mw-heading mw-heading2"><h2 id="Prüfung_auf_Isomorphie_und_Graphen-Isomorphismus-Problem"><span id="Pr.C3.BCfung_auf_Isomorphie_und_Graphen-Isomorphismus-Problem"></span>Prüfung auf Isomorphie und Graphen-Isomorphismus-Problem</h2></div>

<p>Zur Prüfung der Isomorphie zweier gegebener Graphen ist kein effizienter (polynomialzeitlicher) Algorithmus bekannt. Mehr noch, die <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">Komplexität</a> des bestmöglichen Algorithmus ist bis heute noch nicht bestimmt. Insbesondere ist die Isomorphie von Graphen eines der wenigen bekannten Probleme in <a href="NP_(Komplexit%C3%A4tsklasse)" title="NP (Komplexitätsklasse)">NP</a>, für die weder bekannt ist, ob sie in <a href="P_(Komplexit%C3%A4tsklasse)" title="P (Komplexitätsklasse)">P</a> enthalten, noch ob sie <a href="NP-Vollst%C3%A4ndigkeit" title="NP-Vollständigkeit">NP-vollständig</a> sind. Die Frage, ob das Graphen-Isomorphismus-Problem in P ist (oder ob es NP-vollständig ist) ist eines der großen offenen Probleme der Informatik. Es ist das letzte der 12 Probleme in dem Buch <i>Computers and Intractability</i> (1979) von <a href="Michael_Garey" title="Michael Garey">Michael Garey</a> und <a href="David_S._Johnson" class="mw-redirect" title="David S. Johnson">David S. Johnson</a>, von denen nicht bekannt ist, in welche der Komplexitätsklassen NP-vollständig oder P sie gehören (oder nicht gehören). Deshalb wurde es auch schon als eigene Komplexitätsklasse GI definiert und es wurde untersucht, ob andere Probleme GI-schwer oder GI-vollständig sind, wobei die Definitionen in analoger Weise wie bei NP-schwer und NP-vollständig erfolgen.

</p><p><a href="L%C3%A1szl%C3%B3_Babai" title="László Babai">László Babai</a> gab im Dezember 2015 an, einen Algorithmus gefunden zu haben, der das Problem in der Zeit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e^{{(\log {n})}^{O(1)}}}">

<msup>

<msup>

</mrow>

</mrow>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e^{{(\log {n})}^{O(1)}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/be31ba5a76dd5e49013cfa611f9083b300713ac5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.958ex; height:3.343ex;" alt="{\displaystyle e^{{(\log {n})}^{O(1)}}}" loading="lazy"></span> löst (mit der Anzahl <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> der Knoten des Graphen).<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> Dieses Verhalten wird als <i>quasipolynomial</i> bezeichnet, da die Laufzeit schneller als polynomial wächst, aber einem polynomialen Verhalten nahe kommt. Die vorher beste Abschätzung stammte von Babai und <a href="Eugene_Luks" title="Eugene Luks">Eugene Luks</a> 1983,<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> die die Schranke <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e^{O({\sqrt {(n\cdot \log {n})}})}}">

<msup>

<msqrt>

</mrow>

</msqrt>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e^{O({\sqrt {(n\cdot \log {n})}})}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9331810abf2c07b46c940abaa7ebe2d43ba2f4d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.69ex; height:3.176ex;" alt="{\displaystyle e^{O({\sqrt {(n\cdot \log {n})}})}}" loading="lazy"></span> angab.

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

<p>Diese beiden Graphen sind isomorph, obwohl ihre Darstellungen sich erheblich unterscheiden.

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}=(V_{1},E_{1})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ce54faeead4cd211047907a335458e7dc8306daf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{1}=(V_{1},E_{1})}" loading="lazy"></span>

</th>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}=(V_{2},E_{2})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2e832bb526bf16909e2e39f7332a036103557d1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{2}=(V_{2},E_{2})}" loading="lazy"></span>

</th>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\colon V_{1}\to V_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d7b6853cbb7ebfbc0661014c344cb740d931639e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:10.726ex; height:2.509ex;" alt="{\displaystyle p\colon V_{1}\to V_{2}}" loading="lazy"></span>

</th></tr>

<tr>

</td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(a)=1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5082ecbf63a59f913a229778379068b6ea3b103.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:8.559ex; height:2.843ex;" alt="{\displaystyle p(a)=1}" loading="lazy"></span>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(b)=6}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a9f7e685395d8c32e5c736550912191afef2bace.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:8.327ex; height:2.843ex;" alt="{\displaystyle p(b)=6}" loading="lazy"></span>

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(c)=8}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(c)=8}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9cda8cc358d127a3c8b5acb7a05f31cbb70d76a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle p(c)=8}" loading="lazy"></span>

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(d)=3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(d)=3}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6081976936b4cf247fdc6c8c042bd9b26267e8be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:8.545ex; height:2.843ex;" alt="{\displaystyle p(d)=3}" loading="lazy"></span>

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(g)=5}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(g)=5}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f06876ef837a604f138177c6edaf5f64ee6cc212.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:8.445ex; height:2.843ex;" alt="{\displaystyle p(g)=5}" loading="lazy"></span>

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(h)=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(h)=2}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9640990ca0ff6eadda3d564d0e74584fcee8013c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:8.668ex; height:2.843ex;" alt="{\displaystyle p(h)=2}" loading="lazy"></span>

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(i)=4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(i)=4}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d63b6cc046c09ce351af40128dde48b60a559ca8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:8.132ex; height:2.843ex;" alt="{\displaystyle p(i)=4}" loading="lazy"></span>

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(j)=7}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(j)=7}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8a39d400c165b4ee9ef94f829745c1c62d929e41.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:8.287ex; height:2.843ex;" alt="{\displaystyle p(j)=7}" loading="lazy"></span>

</p>

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Software">Software</h2></div>

<ul><li><i><a rel="nofollow" class="external text" href="https://cs.anu.edu.au/people/bdm/nauty/">nauty.</a></i> Ein Programm zur Berechnung der <a href="Automorphismengruppe" class="mw-redirect" title="Automorphismengruppe">Automorphismengruppen</a> und der kanonischen Labelings von Graphen. Zwei Graphen sind genau dann isomorph, wenn ihre kanonischen Labelings übereinstimmen.</li>

<li><a href="NetworkX" title="NetworkX">NetworkX</a>. Eine freie <a href="Python_(Programmiersprache)" title="Python (Programmiersprache)">Python</a>-<a href="Programmbibliothek" title="Programmbibliothek">Bibliothek</a><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Hom%C3%B6omorphie_(Graphentheorie)" class="mw-redirect" title="Homöomorphie (Graphentheorie)">Homöomorphie (Graphentheorie)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Babai: <i><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1512.03547">Graph Isomorphism in Quasipolynomial Time.</a></i> Arxiv 2015. Auf seiner Homepage gab er im Januar 2017 an, dass ein von <a href="Harald_Helfgott" title="Harald Helfgott">Harald Helfgott</a> gefundener Fehler korrigiert werden konnte.</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/2897518.2897542">Babai, Graph isomorphism in quasipolynomial time [extended abstract</a>, STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, Juni 2016, S. 684–697]</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://www.quantamagazine.org/graph-isomorphism-vanquished-again-20170114">Erica Klarreich, Graph isomorphism vanquished - again</a>, Quanta Magazine, Januar 2017</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><a href="#cite_ref-4">↑</a></span> <span class="reference-text">Harald Helfgott, Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...), Seminaire Bourbaki, Nr. 1125, Januar 2017, <a rel="nofollow" class="external text" href="https://arxiv.org/abs/1701.04372">Arxiv</a></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><a href="#cite_ref-5">↑</a></span> <span class="reference-text">László Babai: Groups, Graphs, Algorithms: The Graph Isomorphism Problem. Proc. ICM 2018, Rio de Janeiro, <a rel="nofollow" class="external text" href="https://people.cs.uchicago.edu/~laci/papers/">Online</a></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><a href="#cite_ref-6">↑</a></span> <span class="reference-text">Babai, Luks: <i>Canonical labeling of graphs.</i> Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC ’83), 1983, S. 171–183.</span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><a href="#cite_ref-7">↑</a></span> <span class="reference-text"><span class="cite"><a rel="nofollow" class="external text" href="https://networkx.github.io/documentation/stable/reference/algorithms/isomorphism.html"><i>Algorithms - Isomorphism.</i></a> In: <i>NetworkX 2.2 documentation.</i><span class="Abrufdatum"> Abgerufen am 25. Oktober 2018</span> (englisch).</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3AIsomorphie+von+Graphen&rft.title=Algorithms+-+Isomorphism&rft.description=Algorithms+-+Isomorphism&rft.identifier=https%3A%2F%2Fnetworkx.github.io%2Fdocumentation%2Fstable%2Freference%2Falgorithms%2Fisomorphism.html&rft.language=en"> </span></span>

</li>

</ol>

<div>

Normdaten (Sachbegriff): <a href="Gemeinsame_Normdatei" title="Gemeinsame Normdatei">GND</a>: <span class="-print"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4158050-3">4158050-3</a></span> </div>

</div></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-06-12" href="https://de.wikipedia.org/wiki/?title=Isomorphie_von_Graphen&oldid=256921779">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>